package com.jxb.sort;

import java.util.Arrays;

/**
 * 类注释
 *
 * @author jiaobo
 * @date Created in 2024/12/13 19:47
 **/
public class Sort_912 {

    public static void main(String[] args) {
        int[] nums = {5,2,3,1,4,5,6,7,4,2,4,5,2,3,6,7,3,4,6,7,8,9,0,4,5,6,7,8,9,0,5,5};
        sortArray(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static int[] sortArray(int[] nums) {
        if (nums.length <= 0) {
            return nums;
        }
        //数组长度小于15，通过插入排序的方式
        if (nums.length <= 15) {
            return insertSort(nums);
        }else {
            //数组长度大于15，通过快排的方式
            return quickSort(nums,0,nums.length-1);
        }
    }

    private static int[] quickSort(int[] nums, int start, int end) {
        //通过分区指示器，将数据分成2部分
        int zoneIndex = partition(nums,start,end);
        if (zoneIndex > start) {
            quickSort(nums,start,zoneIndex-1);
        }
        if (zoneIndex < end) {
            quickSort(nums,zoneIndex+1,end);
        }
        return nums;
    }

    private static int[] insertSort(int[] nums) {
        //当前待排序的数据
        int currentValue;
        for (int i = 0;i<nums.length-1;i++) {
            //已被排序的数据索引
            int preIndex = i;
            //获取当前需要排序的数据
            currentValue = nums[preIndex + 1];
            while (preIndex >= 0 && currentValue<nums[preIndex]) {
                nums[preIndex + 1] = nums[preIndex];
                preIndex--;
            }
            nums[preIndex+1] = currentValue;
        }
        return nums;
    }

    public static int partition(int[] array, int start, int end) {
        if (start == end) {
            return start;
        }
        //随机选择一个基数
        int pivot = (int)(start + Math.random()*(end - start + 1));
        //设置分区指示器
        int zoneIndex = start -1;
        //将基准数与分区尾元素交换位置
        swap(array, pivot, end);
        //遍历元素，获取指示器，将数组进行分割
        for (int i = start;i<=end;i++) {
            //当前元素小于等于基准数
            if (array[i] <= array[end]) {
                //将分区指示器加一
                zoneIndex++;
                if (i>zoneIndex) {
                    swap(array,i,zoneIndex);
                }
            }
        }
        return zoneIndex;
    }

    private static void swap(int[] array, int pivot, int end) {
        int temp = array[pivot];
        array[pivot] = array[end];
        array[end] = temp;
    }

}
